package leetcode.map;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;

public class Lc1162 {


    int[] X = {-1, 1, 0, 0};
    int[] Y = {0, 0, -1, 1};
    int[][] midDis;
    int ans = -1;
    HashMap<String, int[]> map = new HashMap<>(); //记录每个海洋位置的最近陆地位置
    public int maxDistance(int[][] grid) {
        int n = grid.length;
        boolean[][] visited = new boolean[n][n];
        midDis = new int[n][n];

        boolean h0 = false, h1 = false;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) h0 = true;
                else  h1 = true;
                if (h0 && h1) break;
            }
            if (h0 && h1) break;
        }

        if (!h0 || h1) return -1;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    getMinDis(i, j, grid, n);
                }
            }
        }
        return ans;
    }

    private void getMinDis(int x, int y, int[][] grid, int n) {
        LinkedList<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x , y});
        boolean[][] visited = new boolean[n][n];
        visited[x][y] = true;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                int[] pos = queue.poll();
                for (int i = 0; i < 4; i++) {
                    int nx = pos[0] + X[i];
                    int ny = pos[1] + Y[i];
                    if (check(nx, ny, n) && !visited[nx][ny]) {
                        if (grid[nx][ny] == 1) {
                            midDis[x][y] = Math.abs(x - nx) + Math.abs(y - ny);
                            ans = Math.max(ans, midDis[x][y]);
                            map.put(x + "_" + y, new int[]{nx, ny});
                            return;
                        } else {
//                            if (midDis[nx][ny] != 0) { //这个方向的最近陆地已经找过，直接判断，不在入队
//                                int[] temp = map.get(nx + "_" + ny);
//                                if (midDis[x][y] < Math.abs(x - temp[0]) + Math.abs(y - temp[1])) {
//                                    midDis[x][y] = Math.abs(x - temp[0]) + Math.abs(y - temp[1]);
//                                    ans = Math.max(ans, midDis[x][y]);
//                                    map.put(x + "_" + y, temp);
//                                }
//                            } else {
                                queue.offer(new int[]{nx, ny});
//                            }
                            visited[nx][ny] = true;
                        }
                    }

                }
            }
        }
    }

    private boolean check(int nx, int ny, int n) {
        if (nx < 0 || nx >= n || ny < 0 || ny >= n)
            return false;
        return true;
    }


    public static void main(String[] args) {
        int[][] g = {{1,0,1},{0,0,0},{1,0,1}};
        Lc1162 lc1162 = new Lc1162();
        System.out.println(lc1162.maxDistance(g));


    }
}
